// An IntSet is a set of small non-negative integers.
// Its zero value represents the empty set.
package intset

import (
	"bytes"
	"fmt"
)

const (
	bitSize = 32 << (^uint(0) >> 63)
)

type IntSet struct {
	words []uint
}

// Has reports whether the set contains the non-negative value x.
func (s *IntSet) Has(x int) bool {
	word, bit := x/bitSize, uint(x%bitSize)
	return word < len(s.words) && s.words[word]&(1<<bit) != 0
}

// Add adds the noe-negative value x to the set.
func (s *IntSet) Add(x int) {
	word, bit := x/bitSize, uint(x%bitSize)
	for word >= len(s.words) {
		s.words = append(s.words, 0)
	}
	s.words[word] |= 1 << bit
}

// UnionWith sets s to hte union of s and t.
func (s *IntSet) UnionWith(t *IntSet) {
	for i, tword := range t.words {
		if i < len(s.words) {
			s.words[i] |= tword
		} else {
			s.words = append(s.words, tword)
		}
	}
}

// String returns the set as a string of the form "{1 2 3}".
func (s *IntSet) String() string {
	fmt.Printf("%T\n", s.words)
	var buf bytes.Buffer
	buf.WriteByte('{')
	for i, word := range s.words {
		if word == 0 {
			continue
		}
		for j := 0; j < bitSize; j++ {
			if word&(1<<uint(j)) != 0 {
				if buf.Len() > len("{") {
					buf.WriteByte(' ')
				}
				fmt.Fprintf(&buf, "%d", bitSize*i+j)
			}
		}
	}
	buf.WriteByte('}')
	return buf.String()
}

// returns the number of the elements
func Len(s *IntSet) int {
	count := 0
	for _, word := range s.words {
		if word == 0 {
			continue
		}
		for j := 0; j < bitSize; j++ {
			if word&(1<<uint(j)) != 0 {
				count++
			}
		}
	}
	return count
}

// remove x from the set
func (s *IntSet) Remove(x int) {
	word, bit := x/bitSize, uint(x%bitSize)
	s.words[word] &= ^(1 << bit)
}

// remove all elements from the set
func (s *IntSet) Clear() {
	s.words = []uint{}
}

// return a copy of the set
func (s *IntSet) Copy() *IntSet {
	var t IntSet
	t.words = make([]uint, len(s.words))
	copy(t.words, s.words)
	return &t
}

// 练习 6.2: 定义一个变参方法(*IntSet).AddAll(...int)，这个方法可以添加一组IntSet，比如 s.AddAll(1,2,3)。
func (s *IntSet) AddAll(x ...int) {
	for _, v := range x {
		s.Add(v)
	}
}

// 交集
func (s *IntSet) IntersectWith(t *IntSet) {
	if len(s.words) > len(t.words) {
		s.words = s.words[:len(t.words)]
	}
	for i, tword := range t.words {
		if i < len(t.words) {
			s.words[i] &= tword
		}
	}
}

// 差集
func (s *IntSet) DifferenceWith(t *IntSet) {
	for i, tword := range t.words {
		if i < len(s.words) {
			s.words[i] &= ^tword
		}
	}
}

// 并差集：元素出现在A但没有出现在B，或者出 现在B没有出现在A
func (s *IntSet) SymmetricDifference(t *IntSet) {
	for i, tword := range t.words {
		if i < len(s.words) {
			s.words[i] ^= tword
		} else {
			s.words = append(s.words, tword)
		}
	}
}

// 练习6.4: 实现一个Elems方法，返回集合中的所有元素，用于做一些range之类的遍历操作。
func (s *IntSet) Elems() []int {
	var elems []int
	for i, word := range s.words {
		if word == 0 {
			continue
		}
		for j := 0; j < bitSize; j++ {
			if word&(1<<uint(j)) != 0 {
				elems = append(elems, bitSize*i+j)
			}
		}
	}
	return elems
}
